package chapter02;

import java.util.Arrays;

public class UniquePaths62 {
    /**
     * 记忆化搜索
     * (0,0)->(m-1,n-1) 多少种走法
     * 递归出口
     *  1)x==m||y==n
     *    return 0
     *  2)x==m-1&&y==n-1
     *    return 1
     *  3)没有出局 返回后续结果
     *    return process(x+1,y)+process(x,y+1)
     *  有些位置(x,y)会反复方便 增加一个dp[x][y]缓存该位置返回结果 节约时间
     *  动态规划
     *  根据递归改动态规划
     */
    //记忆化搜索
    public int uniquePaths(int m, int n) {
        int[][] dp=new int[m+1][n+1];
        for(int i=0;i<dp.length;i++){
            Arrays.fill(dp[i],-1);
        }
        return process(0,0,m,n,dp);
    }

    public int process(int x,int y,int m,int n,int[][] dp){
        if(dp[x][y]!=-1){
            return dp[x][y];
        }
        if(x==m||y==n){
            dp[x][y]=0;
            return dp[x][y];
        }
        if(x==m-1&&y==n-1){
            dp[x][y]=1;
            return dp[x][y];
        }
        dp[x][y]=process(x+1,y,m,n,dp)+process(x,y+1,m,n,dp);
        return dp[x][y];
    }

    //动态规划
    public int uniquePaths1(int m, int n) {
        int[][] dp=new int[m+1][n+1];
        dp[m-1][n-1]=1;
        for(int j=n-2;j>=0;j--){
            dp[m-1][j]=dp[m][j]+dp[m-1][j+1];
        }
        for(int i=m-2;i>=0;i--){
            for(int j=n-1;j>=0;j--){
                dp[i][j]=dp[i+1][j]+dp[i][j+1];
            }
        }
        return dp[0][0];
    }
}
